import random
import time

class CombinationTestGenerator:
    """组合测试数据生成器"""
    
    @staticmethod
    def get_test_cases():
        """获取测试用例"""
        return [
            # 基础用例
            (4, 2, "示例1"),
            (1, 1, "示例2"),
            (3, 2, "3选2"),
            (5, 1, "选1个"),
            (5, 5, "选全部"),
            (6, 3, "6选3"),
            
            # 边界情况
            (2, 1, "最小选择"),
            (10, 1, "大n选1"),
            (8, 4, "中间值"),
        ]
    
    @staticmethod
    def generate_random_case():
        """生成随机测试用例"""
        n = random.randint(5, 12)
        k = random.randint(1, n)
        return (n, k, f"随机n={n},k={k}")
    
    @staticmethod
    def calculate_expected_count(n, k):
        """计算期望组合数 C(n,k)"""
        if k > n or k < 0:
            return 0
        if k == 0 or k == n:
            return 1
        
        k = min(k, n - k)  # 利用对称性优化
        result = 1
        for i in range(k):
            result = result * (n - i) // (i + 1)
        return result


class TestRunner:
    """测试运行器"""
    
    def __init__(self, solution_class):
        self.solution = solution_class()
        self.generator = CombinationTestGenerator()
        self.passed = 0
        self.total = 0
    
    def run_test(self, n, k, description):
        """运行单个测试"""
        self.total += 1
        
        # 执行算法
        start_time = time.time()
        result = self.solution.combine(n, k)
        end_time = time.time()
        
        # 计算期望结果
        expected_count = self.generator.calculate_expected_count(n, k)
        
        # 验证结果
        is_valid = self.validate_result(result, n, k, expected_count)
        
        if is_valid:
            self.passed += 1
            status = "PASS"
        else:
            status = "FAIL"
        
        print(f"测试 {self.total}: {description}")
        print(f"  参数: n={n}, k={k}")
        print(f"  组合数: {len(result)} (期望: {expected_count})")
        print(f"  状态: {status}")
        print(f"  耗时: {(end_time - start_time)*1000:.2f}ms")
        
        # 显示结果（限制显示数量）
        if len(result) <= 10:
            print(f"  结果: {result}")
        else:
            print(f"  结果: {result[:3]} ... {result[-3:]} (共{len(result)}个)")
        
        print("-" * 40)
    
    def validate_result(self, result, n, k, expected_count):
        """验证结果正确性"""
        # 检查组合数量
        if len(result) != expected_count:
            return False
        
        # 检查每个组合
        for combo in result:
            # 检查长度
            if len(combo) != k:
                return False
            
            # 检查元素范围
            if any(num < 1 or num > n for num in combo):
                return False
            
            # 检查是否有序且无重复
            if combo != sorted(set(combo)):
                return False
        
        return True
    
    def run_all_tests(self):
        """运行所有测试"""
        print("组合问题测试")
        print("=" * 40)
        
        # 基础测试
        print("\n基础测试:")
        for n, k, desc in self.generator.get_test_cases():
            self.run_test(n, k, desc)
        
        # 随机测试
        print("\n随机测试:")
        for i in range(3):
            n, k, desc = self.generator.generate_random_case()
            self.run_test(n, k, desc)
        
        # 性能测试
        print("\n性能测试:")
        performance_cases = [
            (10, 5, "10选5"),
            (12, 6, "12选6"),
            (15, 3, "15选3"),
        ]
        for n, k, desc in performance_cases:
            self.run_test(n, k, desc)
        
        # 测试总结
        print("=" * 40)
        print(f"测试完成: {self.passed}/{self.total} 通过")
        print(f"通过率: {self.passed/self.total*100:.1f}%")


# Solution类
class Solution(object):
    def combine(self, n, k):
        result = []
        
        def backtrack(start, path):
            if len(path) == k:
                result.append(path[:])
                return
            
            for i in range(start, n + 1):
                path.append(i)
                backtrack(i + 1, path)
                path.pop()
        
        backtrack(1, [])
        return result


if __name__ == "__main__":
    runner = TestRunner(Solution)
    runner.run_all_tests()
